package cn.edu.xjtu.work.mySqrt;

/**
 * 69. x 的平方根
 * 
 * 实现 int sqrt(int x) 函数。
 * 
 * 计算并返回x的平方根，其中x是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
 */

public class Solution {
  public static void main(String[] args) {
    System.out.println(mySqrt(16));
  }

  /**
   * 二分查找
   * 
   * @param x
   * @return
   */
  public static int mySqrt(int x) {
    int left = 0;
    int right = x;
    int mid;
    while (left <= right) {
      mid = (left + right) / 2;
      if (Math.pow(mid, 2) > x) {
        right = mid - 1;
      } else if (Math.pow(mid, 2) < x) {
        left = mid + 1;
      } else {
        return mid;
      }
    }
    return left - 1;
  }

  /**
   * 暴力待入
   * 
   * @param x
   * @return
   */
  public static int mySqrt1(int x) {
    for (int i = 0; i <= x; i++) {
      double a = Math.pow(i, 2);
      if (a > x) {
        return i - 1;
      } else if (a == x) {
        return i;
      }
    }
    return -1;
  }
}
